package com.leetcode.dynamicplan;

import java.util.Arrays;

/**
 * date:
 * description:
 */
public class Stock188 {
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        int count = Math.min(k, len / 2);
        int[] buy = new int[count + 1];
        int[] sell = new int[count + 1];
        Arrays.fill(buy, Integer.MIN_VALUE);
//        Arrays.fill(sell, 0);
        for(int price : prices){
            for (int i = 1; i <= count; i++) {
                buy[i] = Math.max(buy[i], sell[i - 1] - price);
                sell[i] = Math.max(sell[i], buy[i] + price);
            }
        }
        return sell[count];
    }
}
